package leetcode.code1053;

public class Solution {
	public int[] prevPermOpt1(int[] arr) {
		int len = arr.length;
		int p = len - 1;
		// 从右向左，降序不谈，找逆序位置
		while (p > 0 && arr[p] >= arr[p - 1]) {
			p--;
		}
		if (p == 0) {
			// 从右往左，一直降序，说明原序列升序，没法找到更小的
			return arr;
		}
		int s1 = p - 1;// s1就是待交换的数值，s1右侧一定有数比他小
		// [p,len-1]范围上找到一个小于arr[s1]但是最大的数，这个范围是升序，所以二分找
		int l = p, r = len - 1;
		int s2 = p;
		while (l <= r) {
			int mid = ((r - l) >> 1) + l;
			if (arr[mid] < arr[s1]) {
				if (arr[mid] > arr[s2]) {
					s2 = mid;
				}
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		// 找到了 交换
		this.swap(arr, s1, s2);
		return arr;
	}

	private void swap(int[] arr, int a, int b) {
		int tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}
}
